package com.zjj.algorithm.learning.dmsxl.dynamicplan;

/**
 * 01 背包问题
 * 1、使用二维数据：dp[i][j]
 * [0,i] 物品，任取存放到容量为 j 的背包中
 *
 * @author zjj_admin
 * @date 2023/1/28 21:47
 */
public class DynamicPlan_12_01Package {

    public static void main(String[] args) {

        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        weightBagProblem(weight, value, bagSize);
    }


    /**
     * 01 背包问题解题思路
     * dp[i][j] 表示 [0,i]物品，任取存放到容量为 j 的背包中
     *
     * @param weight
     * @param value
     * @param bagSize
     */
    public static void weightBagProblem(int[] weight, int[] value, int bagSize) {
        int num = weight.length;
        //创建动态规划数组
        int[][] dp = new int[num][bagSize + 1];
        //初始化数组，第一列全部为 0，第一行从第一个物品的重量开始全部初始化成第一个商品的重量【不能从第一列就初始化成 value[0]】
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        //填充 dp 数组
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    //当背包的容量比物品重量小时，就不能够存储物品 i；
                    dp[i][j] = dp[i - 1][j];
                } else {
                    /*
                       当背包可以存放当前物品时就需要进行比较了
                       1、不放物品 i：dp[i][j] = dp[i - 1][j]
                       2、放物品 i：dp[i][j] 为 dp[i - 1][j] 和 dp[i - 1][j - weight[i]] + value[i] 中的最大值
                     */
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < num; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}
